package com.celan.year2023.month10.day06;

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        /*
          dp[i][j] => 第i天，状态为j时的最大利润
          j=0 持有
          j=1 未持有
         */
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; i++) {
            int price = prices[i];
            int hold = dp[i - 1][0];
            int sold = dp[i - 1][1];
            dp[i][0] = Math.max(hold, sold - price);
            dp[i][1] = Math.max(hold + price - fee, sold);
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}